package com.learn.algorithm.graph;

import java.util.*;

public class LeetCode691 {

    public static final int MAXN = 401;
    public static String[] queue = new String[MAXN];
    public static List<List<String>> graph = new ArrayList<>();
    public static Set<String> visited = new HashSet<>();
    public static int l, r;

    static {
        for (int i = 0; i < 26; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public int minStickers(String[] stickers, String target) {
        for (int i = 0; i < 26; i++) {
            graph.get(i).clear();
        }
        visited.clear();

        for (String str : stickers) {
            str = sort(str);
            for (int i = 0; i < str.length(); i++) {
                if (i == 0 || str.charAt(i) != str.charAt(i - 1)) {
                    graph.get(str.charAt(i) - 'a').add(str);
                }
            }
        }
        target = sort(target);
        l = r = 0;
        visited.add(target);
        queue[r++] = target;
        int level = 1;

        while (l < r) {
            int size = r - l;
            for (int i = 0; i < size; i++) {
                String cur = queue[l++];
                for (String s : graph.get(cur.charAt(0) - 'a')) {
                    String next = next(cur, s);
                    if (next.isEmpty()) {
                        return level;
                    } else if (!visited.contains(next)) {
                        visited.add(next);
                        queue[r++] = next;
                    }
                }
            }
            level++;
        }
        return -1;
    }

    public static String sort(String str) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    }

    public static String next(String t, String s) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0, j = 0; i < t.length(); ) {
            if (j == s.length()) {
                builder.append(t.charAt(i++));
            } else {
                if (t.charAt(i) < s.charAt(j)) {
                    builder.append(t.charAt(i++));
                } else if (t.charAt(i) > s.charAt(j)) {
                    j++;
                } else {
                    i++;
                    j++;
                }
            }
        }

        return builder.toString();
    }
}
